package org.pupil.search.binarySearch;

import org.pupil.search.ISearch;

import java.util.Arrays;

/**
 * @Description: 二分搜索：有序数组中找<=num的最右位置
 * @Author: pupil
 * @Date: 2024/08/01 下午 3:20
 */
public class FindRight {

    public static void main(String[] args) {
        // 数据数组最大长度
        int N = 100;
        // 随机数组每个值，在1~V之间随机
        int V = 1000;
        // 测试次数
        int testNumber = 50000;
        System.out.println("测试开始");

        for (int i = 0; i < testNumber; i++) {
            int n = (int) (Math.random() * N);
            int[] arr = ISearch.randomArray(n, V);
            Arrays.sort(arr);
            int num = (int) (Math.random() * N);
            int ans = findRight(arr, num);
            if (ans == -1) {
                System.out.println("没有找到");
            } else {
                System.out.println("找到：" + arr[ans]);
            }
        }
        System.out.println("测试结束");
    }

    /**
     * 有序数组中找<=num的最右位置, 保证数组有序
     *
     * @param arr 数组
     * @param num 目标值
     * @return
     */
    public static int findRight(int[] arr, int num) {
        int l = 0, r = arr.length - 1, m = 0;
        int ans = -1;
        while (l <= r) {
            m = l + ((r - l) >> 1);
            if (arr[m] <= num) { // 中间值 <= num，记录结果，缩小左边范围，往右继续寻找<=num的最右位置
                ans = m;
                l = m + 1;
            } else {  // 中间值 > num，不记录结果，缩小右边范围，往左继续寻找<=num的最右位置
                r = m - 1;
            }
        }
        return ans;
    }
}
